package com.mengfou.nonComparativeSort;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 非比较排序
 * @author mengfou
 * @date 2022-1-7
 */
public class RadixSortDemo2 {
    public static void main(String[] args) {
        int[] arr = new int[]{12, 34, 2, 100, 10, 50,32,6,15};
        new RadixSortDemo2().radixSort(arr);
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }

    public void radixSort(int[] arr){
        int digitalBits = getDigitalBits(arr);
        int[] bucket = new int[arr.length];
        for (int i = 0; i < digitalBits; i++) { // 从个、十、...开始放置在桶中
            int[] count = new int[10];
            for (int item : arr) {
                int number = getNumberByBit(item, i);
                count[number]++;
            }
            // 前缀和数组
            for (int j = 1; j < 10; j++) {
                count[j] += count[j - 1];
            }
            // 从后往前遍历，放置元素
            for (int j = arr.length - 1; j >= 0; j--) {
                int number = getNumberByBit(arr[j], i);
                bucket[count[number] - 1] = arr[j];
                count[number]--;
            }
            System.arraycopy(bucket, 0, arr, 0, arr.length);
        }
    }

    /**
     * 从数组number中获取其个、十等的值
     * @param number 待获取数字
     * @param i 标识位，0表示个位、1表示十位...
     */
    private int getNumberByBit(int number, int i) {
        number = number / (int) Math.pow(10, i);
        return number % 10;
    }

    /**
     * 获取数组arr中最大的数的位数
     * @param arr 待排序数组
     * @return 数组中最大数的位数
     */
    private int getDigitalBits(int[] arr) {
        int maxVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            maxVal = Math.max(maxVal, arr[i]);
        }
        int bit = 0;
        while(maxVal != 0){
            bit++;
            maxVal /= 10;
        }
        return bit;
    }
}
